<?php
/**
 * @title 5473. 灯泡开关 IV - 穷列
 * @author start2004
 */


class Solution {

    /**
     * @param String $target
     * @return Integer
     */
    function minFlips($target) {
        /**
         * @since 2020-07-26 长度
         */
        $len = strlen($target);

        /**
         * @since 2020-07-26 起点
         */
        $init = implode("", array_fill(0, $len, "0"));
        if($init == $target){
            return 0;
        } else {}

        /**
         * @since 2020-07-26 当前可能性集合
         */
        $nexts = [$target];
        $hashs = [
            $target => 1,
        ];

        /**
         * @since 2020-07-26 翻转到本次结果的上1次可能性
         */
        $deep = 1;
        $break = false;
        while($nexts){
            // echo str_repeat(PHP_EOL, 3), "deep={$deep}", PHP_EOL;
            $nextTmp = [];
            foreach ($nexts as $s){
                /**
                 * @since 2020-07-26 依次翻转
                 */
                for($i=$len-1; $i>=0; $i--){
                    if($s[$i] == "0"){
                        $s[$i] = "1";
                    } else {
                        $s[$i] = "0";
                    }
                    // echo "s={$s}", PHP_EOL;

                    /**
                     * @since 2020-07-26 是否回到初始
                     */
                    if($s == $init){
                        $break = true;
                        break;
                    } else {
                        if(!isset($hashs[$s])){
                            $hashs[$s] = 1;
                            $nextTmp[] = $s;
                        } else {}
                    }
                }

                if($break){
                    break;
                } else {}
            }

            if($break){
                break;
            } else {}
            $nexts = $nextTmp;
            $deep++;
        }

        /**
         * @return
         */
        return $deep;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.26_3.php
 */
$datas = [
    // "10111",
    // "101",
    // "00000",
    "001011101",
    // "000101000001010101110010",
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->minFlips($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
